package Leetcode.sliding_window;

/**
 * @Author: kirito
 * @Date: 2024/10/8 16:16
 * @Description:
 * 给你一个下标从 0 开始的 正 整数数组 nums 。
 *
 * 如果 nums 的一个子数组满足：移除这个子数组后剩余元素 严格递增 ，
 * 那么我们称这个子数组为 移除递增 子数组。比方说，[5, 3, 4, 6, 7] 中的 [3, 4] 是一个移除递增子数组，
 * 因为移除该子数组后，[5, 3, 4, 6, 7] 变为 [5, 6, 7] ，是严格递增的。
 *
 * 请你返回 nums 中 移除递增 子数组的总数目。
 *
 * 注意 ，剩余元素为空的数组也视为是递增的。
 *
 * 子数组 指的是一个数组中一段非空且连续的元素序列。
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3,4]
 * 输出：10
 * 解释：10 个移除递增子数组分别为：[1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4] 和 [1,2,3,4]。
 * 移除任意一个子数组后，剩余元素都是递增的。注意，空数组不是移除递增子数组。
 */

public class 统计移除递增子数组的数目 {
    public static void main(String[] args) {
        int[] nums = {8, 7, 6, 6};
        incremovableSubarrayCount(nums);
    }

    /**
     * 本质思想就是找两个递增的前缀和后缀  特殊情况暂不解释
     * 找到前缀  后缀后，中间的都是需要移除的
     * 但是移除多少呢，找第一个 a i < a j的i的索引，然后根据规律
     */
    public static int incremovableSubarrayCount(int[] a) {
        int n = a.length;
        int i = 0;
        while (i < n - 1 && a[i] < a[i + 1]) {
            i++;
        }
        if (i == n - 1) { // 每个非空子数组都可以移除
            return n * (n + 1) / 2;
        }

        int ans = i + 2; // 不保留后缀的情况，一共 i+2 个
        // 枚举保留的后缀为 a[j:]
        for (int j = n - 1; j == n - 1 || a[j] < a[j + 1]; j--) {
            while (i >= 0 && a[i] >= a[j]) {
                i--;
            }
            System.out.println(i);
            // 可以保留前缀 a[:i+1], a[:i], ..., a[:0] 一共 i+2 个
            ans += i + 2;
        }
        return ans;
    }
}
